#include <stdio.h>
#include <stdlib.h>

typedef struct Link
{
    struct Link* pro;
    int elem;
    struct Link* next;
}link;

link* initLink(link* head)
{
    int i;
    // 声明一个指向首元节点的指针
    link* list = NULL;
    // 创建一个首元节点，链表的头指针为head
    head = (link*)malloc(sizeof(link));
    // 对节点初始化
    head->pro = NULL;
    head->next = NULL;
    head->elem = 1;
    list = head;
    for(i=2;i<=5;i++)
    {
        // 创建新节点
        link* body = (link*)malloc(sizeof(link));
        body->pro = NULL;
        body->next = NULL;
        body->elem = i;
        // 新节点与链表最后一个节点建立关系
        list->next = body;
        body->pro = list;
        // 让list始终指向最新节点
        list = body;
    }
    return head;
}

void display(link* head)
{
    link* temp = head;
    while(temp)
    {
        // 判断当前节点是否有后继节点
        if(temp->next == NULL)
        {
            printf("%d\n", temp->elem);
        }
        else
        {
            printf("%d <-> ", temp->elem);
        }
        temp = temp->next;
    }
}

link* insertLink(link* head, int index, int elem)
{
    // 新建一个数据域为elem的节点
    link* temp = (link*)malloc(sizeof(link));
    temp->elem = elem;
    temp->pro = NULL;
    temp->next = NULL;
    /*分三种情况考虑
    1. 插入链表头部
    2. 插入链表中间位置
    3. 插入链表尾部
    */
   if(index == 1)
   {
       temp->next = head;
       head->pro = temp;
       head = temp;
   }
   else
   {
       int i = 0;
       link* body = head;
       // 找到要插入位置前一个节点
       for(i=1;i<index-1;i++)
       {
           body = body->next;
           if(body == NULL)
           {
               printf("插入位置越界...\n");
               return head;
           }
       }
       if(body->next == NULL)
       {
           // 链表尾部插入
           body->next = temp;
           temp->pro = body;
       }
       else
       {
           body->next->pro = temp;
           temp->next = body->next;
           body->next = temp;
           temp->pro = body;
       }
   }
   return head;
}

link* delLink(link* head, int elem)
{
    link* temp = head;
    while (temp)
    {
        if(temp->elem == elem)
        {
            temp->pro->next = temp->next;
            temp->next->pro = temp->pro;
            free(temp);
            temp = NULL;
            return head;
        }
        temp = temp->next;
    }
    printf("链表中没有该节点\n");
    return head;
}

int searchLink(link* head, int elem)
{
    link* temp = head;
    int i = 1;
    while (temp)
    {
        if(temp->elem == elem)
        {
            return i;
        }
        i++;
        temp = temp->next;
    }
    return -1;
}

// 修改链表节点
link* updateLink(link* head, int index, int newElem)
{
    int i = 0;
    link* temp = head;
    for(i = 1; i<index; i++)
    {
        temp = temp->next;
        if(temp == NULL)
        {
            printf("更改位置越界...\n");
            return head;
        }
    }
    temp->elem = newElem;
    return head;
}

int main()
{
    link* head = NULL;
    // 初始化链表
    head = initLink(head);
    display(head);
    // 插入元素
    printf("插入元素100\n");
    head = insertLink(head, 1, 100);
    display(head);
    // 删除链表节点
    printf("删除链表中4节点\n");
    head = delLink(head, 4);
    display(head);
    // 查找链表节点
    printf("3位于链表%d位置\n", searchLink(head, 3));
    // 修改链表节点
    printf("将链表2位置改为1000\n");
    head = updateLink(head, 2, 1000);
    display(head);
    return 0;
}